#include <stdio.h>
#include <stdlib.h>
typedef int ElemType;
// 定义单链表
typedef struct LNode{
    ElemType data; // 存放数据元素
    struct LNode *next; // 指向下一个结点
}LNode;
// 定义链式队列
typedef struct LinkedQueue{
    LNode *front,*rear; // 队列的头、尾指针
}LinkedQueue;

//初始化链式队列(带头指针)
void initQueueWithHead(LinkedQueue &L){
    // 分配头结点，并且头尾指针指向相同
    L.front = L.rear = (LNode*) malloc(sizeof(LNode));
    L.front->next = NULL; // 头结点的下一个结点指向为空
}
//初始化队列(不带头结点)
void initQueue(LinkedQueue &L){
    L.front = NULL;
    L.rear = NULL;
}

//判断队列是否为空(带头结点)
bool isEmpty(LinkedQueue q) {
    if (q.front == q.rear) return true;
    return false;
}
//判断队列是否为空(不带头结点)
bool isEmpty2(LinkedQueue q) {
    if (q.front == NULL) return true;
    return false;
}

// 带头结点的入队操作
bool inQueueWithHead(LinkedQueue &L,ElemType elem){
    LNode *p = (LNode*) malloc(sizeof(LNode));
    if( p == NULL) return false; // 内存不足
    p->data = elem;
    p->next = NULL;
    L.rear->next = p; // 新结点插入到队尾
    L.rear = p; // 队尾指针指向最后一个结点
    return true;
}

// 入队不带头结点
bool inQueue(LinkedQueue &L,ElemType elem){
    LNode *p = (LNode*) malloc(sizeof(LNode));
    if( p == NULL) return false; // 内存不足
    p->data = elem;
    p->next = NULL;
    if(L.front == NULL){ // 队列为空
        L.front = p; // 插入到第1个结点
        L.rear = p;
    }else{
        L.rear->next = p;
        L.rear = p;
    }
    return true;
}

// 出队带头结点
bool outQueueWithHead(LinkedQueue &L,ElemType &elem){
    if(L.front == L.rear) return false; // 队列为空
    LNode *p = L.front->next; // 指向第一个结点
    elem = p->data;
    L.front->next = p->next;
    if(L.rear == p){
        L.rear = L.front; // 仅有一个结点时，出队后，队头和队尾指向同一个
    }
    free(p);
    return true;
}
//出队不带头结点
bool outQueueNoHead(LinkedQueue &L, ElemType &e) {
    if (L.front == NULL) return false; //队列为空
    LNode * p = L.front; // p指向此次出队的结点
    e = p->data;
    L.front = p->next;
    if (L.rear == p) { // p同时也是最后一个结点
        L.front = NULL; //头尾结点都指向NULL
        L.rear = NULL;
    }
    free(p);
    return true;
}
int main() {

    return 0;
}
